LeetCode 108: Convert Sorted Array to Binary Search Tree

題目要求將一個升序排列的數組轉換為一棵高度平衡的二元搜尋樹。

二元搜尋樹的特點:

• 左子樹的所有節點值都小於根節點的值。
• 右子樹的所有節點值都大於根節點的值。

高度平衡樹的定義：

• 一棵二元樹中的每個節點，左右子樹的高度差不能超過 1。這樣可以確保樹的深度盡可能的小，以達到更好的查找效率。

解題思路：

1. 中間元素作為根節點：由於數組是有序的，我們可以選擇數組的中間元素作為根節點，這樣可以保證左右子樹的節點數目差不會太大，從而達到平衡。
2. 遞迴構建子樹：選定根節點後，左半部分的數組對應左子樹，右半部分的數組對應右子樹。我們對每個部分繼續遞迴地構建二元搜尋樹。

程式碼：

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None  # 如果數組為空，返回空樹

        # 選擇中間元素作為根節點
        mid = len(nums) // 2
        root = TreeNode(nums[mid])

        # 遞迴構建左子樹和右子樹
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])

        return root

解題步驟：

1. 基礎檢查：首先檢查數組是否為空，若為空，則返回空樹。
2. 選擇根節點：取數組的中間元素作為根節點，這樣可以保證平衡。
3. 遞迴構建左右子樹：對於中間元素左邊的部分，繼續遞迴構建左子樹；對於右邊的部分，構建右子樹。
   最終返回根節點，代表整個樹。

LeetCode 700: Search in a Binary Search Tree

這個題目要求我們在一棵二元搜尋樹中查找一個指定的值，並返回包含該值的節點。如果該值不存在，則返回 None。

解題思路

因為二元搜尋樹的特性：

• 左子樹的所有節點值都小於根節點的值。
• 右子樹的所有節點值都大於根節點的值。

因此，我們可以根據這些特性來進行搜索：

1. 如果目標值小於當前節點的值，我們應該在左子樹中繼續搜索。
2. 如果目標值大於當前節點的值，我們應該在右子樹中繼續搜索。
3. 如果目標值等於當前節點的值，我們便找到了所需的節點，直接返回該節點。

程式碼

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # 基本情況：當節點為空或者找到目標值時，返回當前節點
        if root is None or root.val == val:
            return root

        # 如果目標值小於當前節點值，繼續在左子樹搜索
        if val < root.val:
            return self.searchBST(root.left, val)

        # 如果目標值大於當前節點值，繼續在右子樹搜索
        return self.searchBST(root.right, val)

解題步驟

1. 基礎檢查：如果當前節點為空，或者我們已經找到了目標值，則直接返回當前節點。
2. 搜索左子樹或右子樹：
   • 如果目標值小於當前節點的值，遞迴搜索左子樹。
   • 如果目標值大於當前節點的值，遞迴搜索右子樹。
3. 返回結果：當找到目標節點時返回該節點，否則返回 None 表示沒有找到。